COMMENT ⊗   VALID 00004 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "lspmac.pub[lsp,clt]" source
C00003 00003	.hd206 Fall 1977
C00019 00004
C00024 ENDMK
C⊗;
.require "lspmac.pub[lsp,clt]" source;
.LSPFONT 
.allop 
.basicops 
.MACRO  hd206 (TERM) ⊂
.BEGIN    NOFILL  TURNON "←→"
←COMPUTER SCIENCE DEPARTMENT
←STANFORD UNIVERSITY
.SKIP  
CS206  ←COMPUTING WITH SYMBOLIC EXPRESSIONS  →TERM
.TURNOFF
.END ⊃
.
.itemmac
.PORTION MAINPORTION
.PAGE ← 1
.hd206 Fall 1977
.skip
.cb Solutions to Midterm Exam.
.skip


(All functions are given in both external and internal form.  The basic auxiliary
functions used in the definitions are presented and explained at the end.)

.BEGIN INDENT 0,4

#. ⊗depth ⊗x is the length of the longest ⊗car-cdr chain reaching an atom
in the S-expression ⊗x.  
.BEGIN NOFILL

⊗⊗        depth x ← qif qat x qthen 0 qelse max[depth qa x, depth qd x] + 1⊗

	$$(DEFUN DEPTH (X) $
	$$       (COND ((ATOM X) 0)$
	$$           (T (PLUS (MAX (DEPTH (CAR X)) (DEPTH (CDR X))) 1))))$
.END

#. Let ⊗u be a list, ⊗f a function mapping S-expressons to lists and ⊗p a predicate
on S-expressions.  Then ⊗⊗mapcat[u, f, p]⊗ is the list obtained by appending
together the lists ⊗f[x] such that ⊗x is an element of ⊗u and ⊗p[x] is true.
.BEGIN NOFILL


⊗⊗        mapcat[u, f, p] ← ⊗
⊗⊗          qif qn u qthen qNIL⊗
⊗⊗          qelse qif p qa u qthen [f qa u * mapcat[qd u, f, p]]⊗
⊗⊗          qelse mapcat[qd u, f, p]⊗

	$$(DEFUN MAPCAT (U F P) $
	$$       (COND ((NULL U) NIL)$
	$$           ((P (CAR U)) (APPEND (F (CAR U)) (MAPCAT (CDR U) F P)))$
	$$           (T (MAPCAT (CDR U) F P))))$
.END

#. Let ⊗g be a directed graph represented as a list of lists, with one sublist
for each vertex in the graph and that sublist  consists of the vertex followed by
a list of vertices to which it is connected.  ⊗⊗component[x, g]⊗  is a list
of all vertices reachable from the vertex ⊗x by some path in the graph ⊗g.  
⊗⊗bigcomponent[x, g⊗] is a list of all vertices connected to ⊗x by any combinatiion
of paths in the graph ⊗g.  

⊗component is computed using the auxiliary function ⊗comp which traces all loop 
free paths from ⊗x, keeping track of all the vertices visited.  
At the ⊗⊗n⊗th call
to ⊗comp, ⊗u is a list of vertices reachable from ⊗x by a path of length ⊗n-1 
(and in fact by no shorter path),  ⊗g is the graph which is just carried along
unchanged throughout the problem, and ⊗seen is a list of vertices already
visited (including those in ⊗u).  ⊗seen is used to avoid visiting a vertex more
than once and hence getting into a loop.  The recursive call to ⊗comp is made
with the first argument getting the list of successors of elements of ⊗u that
have not already been ⊗seen.  The successors of an element ⊗z of ⊗u are just
the vertices ⊗⊗qd assoc[z,_g]⊗. These are appended togther by ⊗mapapp and
duplicates and vertices already ⊗seen are removed by ⊗setdiff.  
 Note that since ⊗assoc is only applied to
⊗⊗x⊗'s that are vertices of ⊗g it will always return a nonempty list so
taking ⊗cdr is safe.
.BEGIN NOFILL

⊗⊗        component[x, g] ← comp[<x>, g, <x>]⊗

	$$(DEFUN COMPONENT (X G) (COMP (LIST X) G (LIST X)))$


⊗⊗        comp[u, g, seen] ← ⊗
⊗⊗          union[u, ⊗
⊗⊗                {setdiff[⊗
⊗⊗                    mapapp[u, $$(LAMBDA (X) (CDR (ASSOC X G)))$], seen]}⊗
⊗⊗                  [λv: qif qn v qthen qNIL⊗
⊗⊗                       qelse comp[v, g, union[v, seen]]]]⊗

	$$(DEFUN COMP (U G SEEN) $
	$$       (UNION U$
	$$            ((LAMBDA (V) (COND ((NULL V) NIL)$
	$$                               (T (COMP V G (UNION V SEEN)))))$
	$$             (SETDIFF (MAPAPP U$
	$$                              '(LAMBDA (X) (CDR (ASSOC X G))))$
	$$                      SEEN))))$
.END



⊗bigcomponent is just ⊗component applied to the undirected graph induced by ⊗g.  
The following solution is fairly compact. The second argument to the call to
⊗component produces the undirected graph corresponding to ⊗g.  It does this
by adding on to the list of vertices to which a given vertex ⊗x is connected, 
all those
vertices connected to ⊗x.  The latter are found using ⊗mapchoose which
chooses ⊗⊗qa w⊗ for each sublist, ⊗w, of ⊗g  such that ⊗⊗xεqd w⊗.
.BEGIN NOFILL

⊗⊗        bigcomponent[x, g] ← ⊗
⊗⊗          component[⊗
⊗⊗            x, ⊗
⊗⊗            mapcar[$$(LAMBDA $⊗
⊗⊗                    $$(X) $⊗
⊗⊗                    $$(CONS $⊗
⊗⊗                     $$(CAR X) $⊗
⊗⊗                     $$(UNION $⊗
⊗⊗                      $$(CDR X) $⊗
⊗⊗                      $$(MAPCHOOSE $⊗
⊗⊗                       $$G $⊗
⊗⊗                       $$(QUOTE (LAMBDA (W) (MEMBER (CAR X) (CDR W)))) $⊗
⊗⊗                       $$(QUOTE (LAMBDA (W) (CAR W))))))), $⊗
⊗⊗                   g]]⊗

	$$(DEFUN BIGCOMPONENT (X G) $
	$$       (COMPONENT$
	$$      X$
	$$      (MAPCAR $
	$$       '(LAMBDA (X) $
	$$                (CONS (CAR X)$
	$$                      (UNION (CDR X)$
	$$                             (MAPCHOOSE G$
	$$                                        '(LAMBDA (W) $
	$$                                                 (MEMBER (CAR X)$
	$$                                                         (CDR W)))$
	$$                                        '(LAMBDA (W) (CAR W))))))$
	$$       G)))$
.END


An alternate way of computing ⊗bigcomponent is given by ⊗bigc.  This function
is like ⊗component but the list of successors from any level is computed by
taking the successors of a vertex ⊗x to be those vertices directly reachable from 
⊗x in ⊗g (namely ⊗⊗qd assoc[x,_g]⊗ )  together with those vertices from which ⊗x 
is directly reachable in ⊗g (namely ⊗⊗invassoc[x,_g]⊗ ).  ⊗comp1 is the auxiliary
function that does the work.
.BEGIN NOFILL

⊗⊗        bigc[x, g] ← comp1[<x>, g, <x>]⊗

	$$(DEFUN BIGC (X G) (COMP1 (LIST X) G (LIST X)))$



⊗⊗        comp1[u, g, seen] ← ⊗
⊗⊗          union[u, ⊗
⊗⊗                {setdiff[⊗
⊗⊗                    mapapp[u, ⊗
⊗⊗                           $$(LAMBDA $⊗
⊗⊗                            $$(X) $⊗
⊗⊗                            $$(UNION $⊗
⊗⊗                             $$(CDR (ASSOC X G)) $⊗
⊗⊗                             $$(INVASSOC X G)))$], ⊗
⊗⊗                    seen]}⊗
⊗⊗                  [λv: qif qn v qthen qNIL⊗
⊗⊗                       qelse comp1[v, g, union[v, seen]]]]⊗

	$$(DEFUN COMP1 (U G SEEN) $
	$$       (UNION U$
	$$            ((LAMBDA (V) (COND ((NULL V) NIL)$
	$$                               (T (COMP1 V G (UNION V SEEN)))))$
	$$             (SETDIFF (MAPAPP U$
	$$                              '(LAMBDA (X) (UNION (CDR (ASSOC X G))$
	$$                                                  (INVASSOC X G))))$
	$$                      SEEN))))$
.END

#. Let ⊗successors ⊗x be the list of successors of an element ⊗x in some search
space, i.e. they are the elements of the space that can be reached from ⊗x in
one move.  ⊗⊗bsearch[x, p]⊗ is an element of the space satisfying the predicate
⊗p and at the least depth in the search tree.   Note that the behaviour of
⊗bsearch is not specified in the case that no element of the search space
satisfies ⊗p.  In the case of an infinite search space with no element 
satisfying ⊗p, ⊗bsearch will not terminate.  If the search space is finite
and no element satisfies ⊗p then something strange may happen when the
space is exhausted (e.g. when ⊗successors returns qNIL).  

.BEGIN NOFILL


⊗⊗        bsearch[x, p] ← bsearch1[<x>, p]⊗

	$$(DEFUN BSEARCH (X P) (BSEARCH1 (LIST X) P))$


⊗⊗        bsearch1[u, p] ← ⊗
⊗⊗          qif p qa u qthen qa u qelse bsearch1[qd u * successors qa u, p]⊗

	$$(DEFUN BSEARCH1 (U P) $
	$$       (COND ((P (CAR U)) (CAR U))$
	$$           (T (BSEARCH1 (APPEND (CDR U) (SUCCESSORS (CAR U))) P))))$
.END
	   

.bb Basic auxiliary functions.

⊗mapapp and ⊗mapchoose belong to the general family of mapping functions discussed
in class.  ⊗mapchoose is like ⊗mapcar except it ignores those elements of ⊗u not
satisfying ⊗p.  
.BEGIN NOFILL


⊗⊗        mapapp[u, fn] ← qif qn u qthen qNIL qelse fn qa u * mapapp[qd u, fn]⊗

	$$(DEFUN MAPAPP (U FN) $
	$$       (COND ((NULL U) NIL)$
	$$           (T (APPEND (FN (CAR U)) (MAPAPP (CDR U) FN)))))$



⊗⊗        mapchoose[u, pred, fn] ← ⊗
⊗⊗          qif qn u qthen qNIL⊗
⊗⊗          qelse qif pred qa u qthen fn qa u . mapchoose[qd u, pred, fn]⊗
⊗⊗          qelse mapchoose[qd u, pred, fn]⊗

	$$(DEFUN MAPCHOOSE (U PRED FN) $
	$$       (COND ((NULL U) NIL)$
	$$           ((PRED (CAR U))$
	$$            (CONS (FN (CAR U)) (MAPCHOOSE (CDR U) PRED FN)))$
	$$           (T (MAPCHOOSE (CDR U) PRED FN))))$
.END



⊗invassoc returns a list of elements which have ⊗x in the list
 associated with them in ⊗g.  ⊗g is a special form of association list in
which each element is associated with a list.
.BEGIN NOFILL

⊗⊗        invassoc[x, g] ← ⊗
⊗⊗          mapchoose[⊗
⊗⊗            g, $$(LAMBDA (W) (MEMBER X (CDR W)))$, $$(LAMBDA (W) (CAR W))$]⊗

	$$(DEFUN INVASSOC (X G) $
	$$       (MAPCHOOSE G$
	$$                '(LAMBDA (W) (MEMBER X (CDR W)))$
	$$                '(LAMBDA (W) (CAR W))))$
.END



⊗union returns the list consisting of the set of elements ⊗x such that ⊗⊗xεu⊗
or ⊗⊗xεv⊗.  Lists representing sets are assumed to have no duplications of 
elements.
.BEGIN NOFILL

⊗⊗        union[u, v] ← ⊗
⊗⊗          qif qn u qthen v⊗
⊗⊗          qelse qif qa u ε v qthen union[qd u, v]⊗
⊗⊗          qelse qa u . union[qd u, v]⊗

	$$(DEFUN UNION (U V) $
	$$       (COND ((NULL U) V)$
	$$           ((MEMBER (CAR U) V) (UNION (CDR U) V))$
	$$           (T (CONS (CAR U) (UNION (CDR U) V)))))$
.END


⊗setdiff returns a list consisting of the set of elements ⊗x such that ⊗⊗xεu⊗
and ⊗⊗¬xεv⊗.  ⊗u and ⊗v are not necessarily repetition free. 
.BEGIN NOFILL

⊗⊗        setdiff[u, v] ← ⊗
⊗⊗          qif qn u qthen qNIL⊗
⊗⊗          qelse qif qa u ε v ∨ qa u ε qd u qthen setdiff[qd u, v]⊗
⊗⊗          qelse qa u . setdiff[qd u, v]⊗

	$$(DEFUN SETDIFF (U V) $
	$$       (COND ((NULL U) NIL)$
	$$           ((OR (MEMBER (CAR U) V) (MEMBER (CAR U) (CDR U)))$
	$$            (SETDIFF (CDR U) V))$
	$$           (T (CONS (CAR U) (SETDIFF (CDR U) V)))))$
.END
.END